package lc.q51_100;

import java.util.Stack;

/**
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 *
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 */
public class Q84 {

    public int largestRectangleArea(int[] heights) {
        if (heights.length == 0) {
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int max = heights[0];
        for (int i = 0; i < heights.length; i++) {
            while (stack.size() > 1 && heights[i] < heights[stack.peek()]) {
                Integer pop = stack.pop();
                // 将比i大的数都抛出来，就能够计算出前面的最大值了
                int len = i - stack.peek() - 1;
                max = Math.max(heights[pop] * len, max);
            }
            stack.push(i);
        }
        while (stack.peek() != -1) {
            max = Math.max(max, heights[stack.pop()]*(heights.length - stack.peek() - 1));
        }
        return max;
    }

    public static void main(String[] args) {
        Q84 q84 = new Q84();
        System.out.println(q84.largestRectangleArea(new int[]{2,1,5,6,2,3}));
    }

}
